/// @tags: Muodui
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

constexpr int N = 1e5 + 5, BLK = 350;

int n, m, A[N], sum[N], cnt[N], ans[N], sqrxp[N], txp[N];

struct Node {
  int l, r, id, P;

  inline bool operator<(const Node &b) const {
    if (l / BLK == b.l / BLK) {
      return r < b.r;
    }
    return l < b.l;
  }
} q[N];

struct LinkList {
  int nxt[N], pre[N], head;
  inline void add(int a) {
    pre[a] = 0, nxt[a] = head;
    pre[head] = a;
    head = a;
  }

  inline void delet(int a) {
    if (a == head) {
      int _nxt = nxt[a];
      pre[_nxt] = -1;
      head = _nxt;
    } else {
      int _nxt = nxt[a], _pre = pre[a];
      nxt[_pre] = _nxt;
      pre[_nxt] = _pre;
    }
  }
} list;

inline void update(int pos, int delta) {
  int val = A[pos];
  sum[cnt[val]] -= val;
  if (!sum[cnt[val]]) list.delet(cnt[val]);
  cnt[val] += delta;
  if (!sum[cnt[val]]) list.add(cnt[val]);
  sum[cnt[val]] += val;
}

inline LL qpow(int x, int P) { return (LL)sqrxp[x / BLK] * txp[x % BLK] % P; }

inline void prework(int P) {
  txp[0] = sqrxp[0] = 1;
  for (int j = 1; j <= BLK; ++j) txp[j] = txp[j - 1] * 2LL % P;
  for (int j = 1; j <= BLK; ++j) sqrxp[j] = (LL)sqrxp[j - 1] * txp[BLK] % P;
}

inline int inc(int x, int y, int P) {
  x += y;
  return x >= P ? x - P : x;
}

inline int dec(int x, int y, int P) {
  x -= y;
  return x < 0 ? x + P : x;
}

inline int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> A[i];
  }
  for (int i = 1; i <= m; ++i) {
    cin >> q[i].l >> q[i].r >> q[i].P;
    q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  int L = 1, R = 0;
  for (int i = 1; i <= m; ++i) {
    int l = q[i].l, r = q[i].r, id = q[i].id, P = q[i].P;
    prework(P);
    while (L > l) update(--L, 1);
    while (R < r) update(++R, 1);
    while (L < l) update(L++, -1);
    while (R > r) update(R--, -1);
    for (int j = list.head; j > 0; j = list.nxt[j]) {
      ans[id] =
          inc(ans[id],
              (LL)sum[j] * dec(qpow(r - l + 1, P), qpow(r - l + 1 - j, P), P) % P, P);
    }
  }
  for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P5072 [Ynoi2015] 盼君勿忘.in", "r", stdin);
  freopen("P5072 [Ynoi2015] 盼君勿忘.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
